package com.zsk.algorithm;

/**
 * 排序算法
 * 
 * @author keke
 * @date 2020/05/12
 */
public class Sort {

    /**
     * 冒泡排序<br>
     * 时间复杂度o(n2)，空间复杂度o(1)
     * 
     * @param nums
     */
    public static void bubbleSort(int[] nums) {
        int tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
    }

    /**
     * 比较排序<br>
     * 时间复杂度o(n2)，空间复杂度o(1) 说明：<br>
     * 1.循环每个元素<br>
     * 2.和剩下每个元素逐一比较，大于或小于就交换位置<br>
     * 
     * @param nums
     */
    public static void compareSort(int[] nums) {
        int tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                }
            }
        }
    }

    /**
     * 选择排序<br>
     * 时间复杂度o(n2)，空间复杂度o(1)<br>
     * 说明：<br>
     * 1.循环每个数组的每个位置<br>
     * 2.在剩余未排序的元素中找到最小(大)的元素放在当前位置上
     * 
     * @param nums
     */
    public static void selectSort(int[] nums) {
        int tmp = 0;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            index = i;
            for (int j = i; j < nums.length; j++)
                if (nums[index] > nums[j])
                    index = j;

            tmp = nums[i];
            nums[i] = nums[index];
            nums[index] = tmp;
        }
    }

    /**
     * 快速排序（核心是分治思想）<br>
     * 1. low，high分别表示最左，最右的索引 <br>
     * 2. 以最左位置设定基准为，当左索引小于右索引时，从右向左找到比基准为小的数，从左向右找到比基准为大的数，然后交换 <br>
     * 3. 当左右索引相遇时将基准位和该位置交换<br>
     * 4. 以左右索引相遇位置为分割点，递归左边数组，递归右边数组
     * 
     * @param data
     * @date 2019/10/29 14:43:17
     * @author zincredible
     */
    public static void quickSort(int[] data, int low, int high) {
        if (low > high) {
            return;
        }
        int temp = 0;
        // 以第一个元素为基准数
        int base = data[low];
        // 低位起始扫描位置
        int i = low;
        // 高位起始扫描位置
        int j = high;
        while (i < j) {
            // 因为基准数设置为第一个元素，即最左边的元素，所以每次必须从右边开始探测
            // 从右向左扫描找到小于基准数的位置停下来
            while (base <= data[j] && i < j) {
                j--;
            }
            // 从左向右扫描找到大于基准数的位置停下来
            while (base >= data[i] && i < j) {
                i++;
            }
            // 当i<j时说明i比标准元素大，j表标准元素小，将i放到基准元素右侧，j放到基准元素左侧
            if (i < j) {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        // 将基准位数据调整到i和j相遇的位置，将i=j的位置元素调整到原来基准位
        data[low] = data[i];
        data[i] = base;
        // 继续分治
        // 递归调用左半数组
        quickSort(data, low, j - 1);
        // 递归调用右半数组
        quickSort(data, j + 1, high);
    }

    public static void print(int[] nums) {
        for (int i : nums) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] nums = new int[] {10, 5, 1, 45, 200, 78, 9, 0};
        print(nums);
        quickSort(nums, 0, nums.length - 1);
        print(nums);
    }
}
